package leetcode.l0527;

import leetcode.l0526.Easy_环形链表_141;

import java.util.HashSet;

/**
 * @author Retain
 * @date 2021/5/27 10:45
 */
public class Easy_相交链表_160 {

    public static void main(String[] args) {
//                [4,1,8,4,5]
//              [5,6,1,8,4,5]
        ListNode Anode1 = new ListNode(4);
        ListNode Anode2 = new ListNode(1);
        ListNode Bnode1 = new ListNode(5);
        ListNode Bnode2 = new ListNode(6);
        ListNode Bnode3 = new ListNode(1);
        ListNode node1 = new ListNode(8);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(5);

        Anode1.next = Anode2;
        Anode2.next = node1;
        node1.next = node2;
        node2.next = node3;
        Bnode1.next = Bnode2;
        Bnode2.next = Bnode3;
        Bnode3.next = node1;
        System.out.println(getIntersectionNode(Anode1, Bnode1).val);
    }

    /**
     * Hash表法，如果add失败，则存在相交链表
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> nodes = new HashSet<>();

        while (headA != null) {
            if (!nodes.add(headA)) {
                return headA;
            }
            headA = headA.next;
        }
        while (headB != null) {
            if (!nodes.add(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 双指针法，A走完遍历B，B走完遍历A，如果在最后结点相遇或者路程相等，那么链表相交
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        // 特判
        if (headA == null || headB == null) {
            return null;
        }

        ListNode head1 = headA;
        ListNode head2 = headB;

        while (head1 != head2) {
            if (head1 != null) {
                head1 = head1.next;
            } else {
                head1 = headB;
            }

            if (head2 != null) {
                head2 = head2.next;
            } else {
                head2 = headA;
            }
        }
        return head1;
    }

}
